#pragma once
#include <vector>

template <typename Comparable>
class BinaryHeap
{
public:
	explicit BinaryHeap(int capacity = 100)
	{
		currentSize = 0;
		array.reserve(101);
	}
	explicit BinaryHeap(const std::vector<Comparable> & items)
	{
		for (int i = 0; i < items.size(); i++)
			array[i+1] = items[i];
		buildHeap();
	}

	bool isEmpty() const
	{
		return currentSize == 0;
	}
	const Comparable & findMin() const
	{
		return array[1];
	}

	void insert(const Comparable & x)
	{
		if (currentSize == array.size() - 1)
			array.resize(array.size() * 2);

		int hole = ++currentSize;
		for ( ; hole > 1 && x < array[hole / 2]; hole /= 2)
			array[hole] = array[hole / 2];
		array[hole] = x;
	}

	int deleteMin()
	{
		if (isEmpty())
			return -1;
		array[1] = array[currentSize--];
		percolateDown(1);
	}
	int deleteMin(Comparable & minItem)
	{
		if (isEmpty())
			return -1;
		minItem = array[1];
		array[1] = array[currentSize--];
		percolateDown(1);
	}

	void makeEmpty()
	{
		currentSize = 0;
	}

private:
	int currentSize;
	std::vector<Comparable> array;

	void buildHeap()
	{
		for (int i = currentSize /2; i > 0; i--)
			percolateDown(i);
	}

	void percolateDown(int hole)
	{
		int child;
		Comparable tmp = array[hole];
		for ( ; hole*2 <= currentSize; hole = child)
		{
			child = hole *2;
			if (child != currentSize && array[child+1] < array[child])
				child++;
			if (array[child] < tmp)
				array[hole] = array[child];
			else
				break;
		}
		array[hole] = tmp;
	}
};
